\documentclass[main]{subfiles} 

\begin{document}
	\section{搜索复习、搜索剪枝【20250112】}
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc271\_d\#author=DeepSeek\_zh}{AtCoder-abc271\_d}}
	$succeed_{i,j}$表示前$i$个二元组选中的数的和为$j$时通过后续的选择是否能够满足所有的选中的数的和为$S$
	
	$$
	succeed_{i,j} =
	\begin{cases}
		succeed_{i+1,j+a_{i+1}}\  or\  succeed_{i+1,j+b_{i+1}} &if\ i<N\\
		True &if\ i=N  , j=S
	\end{cases}
	$$
	
	具体实现时考虑到$j$的稀疏性，用记忆化搜索会比较好。
	
	有解时可以根据$succeed$构造出选择方案。
	
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1731}{洛谷-P1731}}
	经典的DFS问题，从底层向顶层开始DFS枚举每层蛋糕的$R_i$和$H_i$然后加些剪枝就可以AC。
	
	
	剪枝：
	\begin{itemize}
		\item 如果算上当前层往上数还有$Dep$层，则$R$和$H$的最小值为$Dep$，最大值分别不超过底下一层的$R$和$H$
		\item 当前状态下可以计算出剩余的部分的$V_{max},V_{min},S_{min}$，分别做可行性和最优性剪枝
		\item 我想过用$unordered\_map$存下所有的$V_{max}$，但是实践发现会TLE
	\end{itemize}
	
	\subsection{\href{https://vjudge.net/problem/UVA-12558\#author=IcecreamArtist}{UVA-12558}}
	迭代加深DFS在加些剪枝即可。
	
	枚举$\frac{1}{d}$时的剪枝：
	\begin{itemize}
		\item 当前还剩$dep$项，这$dep$项的和为$rest$，则$\frac{dep}{d}\leq rest$
		\item $d<=max\_d$
	\end{itemize}
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1106D\#author=DeepSeek\_zh}{CodeForces-1106D}}
	模仿Prim算法以1为根，每次选标号最小的顶点加入到生成树中，加点顺序即为答案。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P2324}{洛谷-P2324}}
	折半BFS，从末状态出发走8步的这一半BFS可以预处理，每次询问从初状态BFS走至多7步。
	
	\subsection{\href{https://vjudge.net/problem/AtCoder-abc328\_e\#author=DeepSeek\_zh}{AtCoder-abc328\_e}}
	模仿Prim算法以$1$号点为根DFS不断加一个点生成一棵子树，记录下这个子树中边权和$Mod\ K$的值作为Hash记录在当前联通的点集对应的$unordered\_set$中即可。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1118\#author=DeepSeek_zh}{洛谷-P1118}}
	DFS按照字典序枚举$1 \dots N$的全排列，预处理出每个位置上的数加到最顶端的$S$时加了多少次。通过这些系数可以计算出当前剩余的数字能够得到的$S$的上下界，将这个上下界用于剪枝。
	
	\subsection{\href{https://vjudge.net/problem/OpenJ\_Bailian-1165\#author=GPT\_zh}{OpenJ\_Bailian-1165}}
	首先打质数表：
	\begin{itemize}
		\item $list[i][j][k]$表示以$i$开头，末尾$j+1$位为$k$，且数码和为$sum$的质数表
		\item $right_down_prime$表示能放在第5行和第5列，且数码和为$sum$的质数表
	\end{itemize}
	
	然后直接枚举，枚举顺序是这样的：
	\begin{enumerate}
		\item 枚举第5行和第5列
		\item 枚举第1行
		\item 枚举第1列
		\item 枚举第4列
		\item 枚举第3列
	\end{enumerate}
	
	在上述的每一步枚举过程中就可以用打出的表来判断是否有解，完成上述枚举过程后可以直接算出第2列，然后再检查整个矩阵是否符合要求，最后把所有的答案排序后输出。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1074}{洛谷-P1074}}
	NOIP2009提高组的原题，当年在考场上没有写出来。
	
	因为权值按照靶形分布，所以其实最高和最低分数相差不会很大，用分数剪枝效果不理想。正确的做法是DFS中每次选可选择数字最少的格子枚举，然后在所有的方案中求出最高分数。用二进制状态来表示每一行，每一列，每个小方块中还能使用哪些数字。
	
	\subsection{\href{https://vjudge.net/problem/LibreOJ-10021}{LibreOJ-10021}}
	迭代加深DFS，开个$Hash$记录一下当前函数的循环中出现过的数字，避免$a_{dep}=a_i+a_j=a_k+a_l$导致的重复计算。
	
	PS：后面试了一下，不加这个直接暴力搜索也能过。
	
	
\end{document}